// 二分搜索框架：

int binarySearch(int[] nums, int target)
{
	int left = 0, right = ...;

	while(...)
	{
		int mid = left + (right - left) / 2;

		if(nums[mid] == target)
		{
			...
		}
		else if(nums[mid] < target)
		{
			left = ...
		}
		else if(nums[mid > target)
		{
			right = ...
		}
	}
	
	return ...;
}


// 最简单的二分查找题
class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
        int left = 0, right = nums.size() - 1; // 左闭右闭 []

        while(left <= right)
        {
            int mid = left + (right - left) / 2; // 防止left和right值太大导致溢出

            if(nums[mid] == target)
            {
                return mid;
            }
            else if(nums[mid] < target)
            {
                left = mid + 1;
            }
            else if(nums[mid] > target)
            {
                right = mid - 1;
            }
        } 

        return -1;
    }
};


// 在排序数组中查找元素的第一个和最后一个位置
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        vector<int> res; // 用于记录结果
        int ret1 = 0, ret2 = 0; // 分别记录左右边界

        ret1 = left_bound(nums, target);
        res.push_back(ret1);

        ret2 = right_bound(nums, target);
        res.push_back(ret2);

        return res;

    }

    // 还是要注意封装代码啊！避免一些不必要的错误

        int left_bound(vector<int>& nums, int target) {
        int left = 0, right = nums.size()-1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 别返回，锁定左侧边界
                right = mid - 1;
            }
        }
        // 判断 target 是否存在于 nums 中
        if (left < 0 || left >= nums.size()) {
            return -1;
        }
        // 判断一下 nums[left] 是不是 target
        return nums[left] == target ? left : -1;
    }

    int right_bound(vector<int>& nums, int target) {
        int left = 0, right = nums.size()-1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 别返回，锁定右侧边界
                left = mid + 1;
            }
        }
        // 判断 target 是否存在于 nums 中
        // if (left - 1 < 0 || left - 1 >= nums.size()) {
        //     return -1;
        // }
        
        // 由于 while 的结束条件是 right == left - 1，且现在在求右边界
        // 所以用 right 替代 left - 1 更好记
        if (right < 0 || right >= nums.size()) {
            return -1;
        }
        return nums[right] == target ? right : -1;
    }
};


// 在排序数组中查找元素的第一个和最后一个位置
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        vector<int> res; // 用于保存结果
        int ret1 = 0, ret2 = 0; // 用于记录左右边界

        ret1 = leftBound(nums, target);
        res.push_back(ret1);

        ret2 = rightBound(nums, target);
        res.push_back(ret2);

        return res;
    }

    // 查找左侧边界
    int leftBound(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1;

        while(left <= right)
        {
            int mid = left + (right - left) / 2;

            if(nums[mid] < target)
            {
                // 搜索区间更改为[mid+1,right]
                left = mid + 1;
            }
            else if(nums[mid] > target)
            {
                // 搜索区间更改为[left, mid-1]
                right = mid - 1;
            }
            else if(nums[mid] == target)
            {
                // 收缩右侧边界
                right = mid - 1;
            }
        }

        // 判断target是否在nums中
        if(left < 0 || left >= nums.size())
            return -1;

        // 判断nums[left]是不是target
        return nums[left] == target ? left : -1;
    }

    // 查找右侧边界
    int rightBound(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1;

        while(left <= right)
        {
            int mid = left + (right - left) / 2;

            if(nums[mid] < target)
            {
                // 搜索区间更改为[left+1, right]
                left = mid + 1;
            }
            else if(nums[mid] > target)
            {
                // 搜索区间更改为[left, mid-1]
                right = mid - 1;
            }
            else if(nums[mid] == target)
            {
                // 收缩左侧边界
                left = mid + 1;
            }
        }

        // 判断target是否在nums中
        if(right < 0 || right >= nums.size())
            return -1;

        // 判断nums[right]是不是target
        return nums[right] == target ? right : -1;
        
    }
};


// 在排序数组中查找数字I
class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
        int left = leftBound(nums, target);
        int right = rightBound(nums, target);

        if(left == -1 || right == -1)
            return 0;

        return right - left + 1;
    }

    // 查找左侧边界
    int leftBound(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1;

        while(left <= right)
        {
            int mid = left + (right - left) / 2;

            if(nums[mid] < target)
            {
                // 搜索区间更改为[mid+1,right]
                left = mid + 1;
            }
            else if(nums[mid] > target)
            {
                // 搜索区间更改为[left, mid-1]
                right = mid - 1;
            }
            else if(nums[mid] == target)
            {
                // 收缩右侧边界
                right = mid - 1;
            }
        }

        // 判断target是否在nums中
        if(left < 0 || left >= nums.size())
            return -1;

        // 判断nums[left]是不是target
        return nums[left] == target ? left : -1;
    }

    // 查找右侧边界
    int rightBound(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1;

        while(left <= right)
        {
            int mid = left + (right - left) / 2;

            if(nums[mid] < target)
            {
                // 搜索区间更改为[left+1, right]
                left = mid + 1;
            }
            else if(nums[mid] > target)
            {
                // 搜索区间更改为[left, mid-1]
                right = mid - 1;
            }
            else if(nums[mid] == target)
            {
                // 收缩左侧边界
                left = mid + 1;
            }
        }

        // 判断target是否在nums中
        if(right < 0 || right >= nums.size())
            return -1;

        // 判断nums[right]是不是target
        return nums[right] == target ? right : -1;
        
    }
};



// 两数之和问题：
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) 
    {
        int left = 0, right = numbers.size() - 1;

        while(left < right)
        {
            int sum = numbers[left] + numbers[right];

            if(sum == target)
            {
                return {left + 1, right + 1};
            }
            else if(sum < target)
            {
                left++;
            }
            else if(sum > target)
            {
                right--;
            }
        }

        return {-1, -1};
    }
};


// 反转字符串
class Solution {
public:
    void reverseString(vector<char>& s) 
    {
        int left = 0, right = s.size() - 1;

        while(left < right)
        {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;

            left++;
            right--;
        }
    }
};


